1. Field of the Invention
The present invention relates to a method and an apparatus for checking a pipelined parallel cyclic redundancy, and in particular, to a method and an apparatus for checking a pipelined parallel cyclic redundancy wherein, after an entire CRC (cyclic redundancy check) logic is divided into a feedback portion and an input data portion, the input data portion is divided using a pipelined structure such that the input data portion is designed to have the pipelined structure based on an algorithm that maintains a logic level of each stage to be lower than that of the feedback portion and an algorithm that optimizes a size of a register inserted during the division to improve a speed thereof and to detect an error of a received data in a high speed data communication apparatus.
2. Description of Prior Art
The CRC is a most widely used method for detecting an error in a data communication system. For instance, Korean Patent No. 126591, titled “PARALLEL CIRCULATION REDUNDANCY MONITORING CODE GENERATION MEANS FOR HIGH TRANSPORT PROTOCOL CHECK CODE GENERATION” filed by Electronics and Telecommunications Research Institute on Dec. 13, 1994 and registered on Oct. 16, 1997 discloses a means for generating a CRC data in detail.
Specifically, a transmitter and a receiver uses a predetermined number as a divisor to divide a data to be transmitted by the transmitter by the predetermined number. A remainder is then attached to the data to be transmitted. The receiver compares a remainder by dividing a received data by the predetermined number, or checks whether the remainder is zero by dividing a received data including the remainder by the predetermined number to check an error of the data. During the process, the remainder itself is the CRC code, and the CRC code is always smaller than the predetermined number since the CRC code is the remainder obtained by the division by the predetermined number.
Based on this principle, a current data communication system employs a few polynomials standardized as the divisor, and a result obtained by carrying out an operation with a binary module is used as the CRC code.
Therefore, in a serial data communication system, since an XOR gate may be used to carry out the operation, a LFSR (Linear Feedback Shift Register) and the XOR gate may be used for a realization.
FIG. 1 is a diagram illustrating an example of a conventional CRC generator. The conventional CRC generator of FIG. 1 employs the LFSR for a polynomial P(x)=x16+x12+x5+1 (compliant to ITU_TSS standard).
As shown, the CRC corresponding to the polynomial P (x)=x16+x12+x5+1 is generated by adding a data value shifted by a plurality of LFSRs F1 through F16.
As shown in FIG. 1, the serial CRC generation obstructs an improvement of a system speed. Therefore, a research on a method wherein the CRC code is generated in one clock cycle after a serial data is converted to a parallel data has be conducted. As a result, a CRC generation circuit wherein the parallel data is inputted and the CRC data is generated in one cycle through a XOR combination circuit has been developed instead of the conventional serial CRC generation wherein the CRC data is stored in each flip-flop after a plurality of shifts and an XOR operation.
FIG. 2 is a diagram illustrating a pseudo code of a conventional CRC generation algorithm for obtaining a combination of Xi that generates a result of each registers after n number of shifts. The result stored in each F for every loop is represented as Xi instead of a calculated number to obtain the combination of Xi as shown in FIG. 3. Referring to FIG. 2, an embodiment of a basic parallel CRC circuit may be generalized as follows.
In order to describe an algorithm for embodying n-bit CRC generator wherein a size of the parallel data and a length of a CRC register are a positive integer n, it is assumed that I is a positive integer equal to or smaller than n (i=1, 2, . . . , n) for a n-bit LFSR, Fi is an i-th register of the LFSR, Ci is an initial value stored in Fi prior to a shift, Di is an i-th input data, a data is inputted from a least significant bit D1, and the shift progresses to a direction of low number register as shown in FIG. 1.
The initial value Ci of the register prior to the shift differs according to the CRC generation method. The initial value Ci may be set as ‘1’, ‘0’ or alternating ‘1’ and ‘0’.
In accordance with the CRC generation, one bit is shifted for each clock to store a new value consisting of a combination of each of Ci and Di by the shift and the XOR gate in the register Fi.
For instance, after one shift in FIG. 1, F16 stores (D1 XOR C1), F11 stores (D1 XOR C1 XOR C12), F4 stores (D1 XOR C1 XOR C5), and other registers simply stores Fi+1. In a similar manner, values stored in each of the registers after n number of shifts are the CRC code for the n-bit data. In addition, if Xi is (Di XOR Ci), the values stored in the registers after the n number of shifts only include a combination of Xi. Therefore, one Xi is two XOR gate and the parallel CRC circuit for generating the CRC code in one clock from the combination of Xi may be embodied.
FIG. 3 is a diagram illustrating a CRC result having the pseudo code applied thereto. In FIG. 3, a result wherein the pseudo code of FIG. 2 is applied to the polynomial P (x)=x16+x12+x5+1 (compliant to ITU_TSS standard). An operation value of X4 XOR X5 XOR X8 XOR X12 XOR X16 is stored in F1, and an operation value of X5 XOR X6 XOR X9 XOR X13 is stored in F16.
On the other hand, while FIGS. 2 and 3 illustrates a case wherein the size of the parallel data and the length of the CRC register is the positive integer n, a general case wherein the size of the parallel data is w and the length of the CRC register is the positive integer n may be embodied by Equation 1.
                    F        =                  [                                                                      p                                      n                    -                    1                                                                              1                                            0                                            ⋯                                            0                                                                                      p                                      n                    -                    2                                                                              0                                            1                                            ⋯                                            0                                                                    ⋯                                            ⋯                                            ⋯                                            ⋯                                            ⋯                                                                                      p                  1                                                            0                                            0                                            ⋯                                            1                                                                                      p                  0                                                            0                                            0                                            ⋯                                            0                                              ]                                    [                  Equation          ⁢                                          ⁢          1                ]            
Using the conversion matrix F, the CRC may be expressed as Equation 2 where the parallel data D is D=[dw-1, dw-2, . . . d0|0, . . . , 0]T when w<n, D=[dw-1, dw-2, . . . d0]T when w=n, and the CRC code C is C=[cn-1, cn-2, . . . c0]T.CRC=Fw{circle around (x )}(C⊕D)   [Equation 2]
{circle around (x )} is an operator denoting a matrix multiplication and ⊕ is an operator denoting an XOR operation of the matrix.
A detailed description of the method is disclosed in a paper by G. Campobello, G. Patane and M. Russo, titled “Parallel CRC Realization,” IEEE Transactions on Computers, Vol. 52, pp. 63-71, October, 2003.
FIG. 4 is a diagram illustrating an example of a conventional CRC generation circuit.
The conventional CRC generation circuit of FIG. 4 is embodies based on Equation 1, and a basic parallel CRC circuit using a Din register 110 of w bits, a CRC register 120 of n bits and a CRC result table is shown.
That is, an input data is Din of w bits, and the input data is stored in the Din register 110. In addition, a CRC_Code of n bits is outputted by the CRC register 120 of n bits for storing the CRC result table, an XOR logic 130 for carrying out an XOR operation based on the CRC table of n bits and Din of w bits.
Examples of the conventional CRC circuit may be referred from papers below.
A paper by D. V. Sarwate, titled “Computation of Cyclic Redundancy Checks via Table Look-Up,” Comm. ACM, August, 1988, a paper by S. M. Joshi, P. K. Dubey and M. A. Kaplan, titled “A New Parallel Algorithm for CRC Generation,” IEEE International Conference on Communications, Vol. 3, pp. 18-22, Jun. 2000 disclose the generation of the CRC using a table search method. However, it is disadvantageous in that a time required for searching the table is increased as an order and a data width of a code generation polynomial are increased.
In addition, a paper by T. B. Pei and C. Zukowski, titles “High-Speed Parallel CRC Circuits in VLSI”, IEEE Transaction on Communications, Vol. 40, no. 4, pp. 653-657, 1992 discloses a 32-bit CRC circuit having a input data width of 8 bits using a result after eight shifts of a 32-bit LFSR.
A paper by R. F. Hobson and K. L. Cheng, titled “A High-Performance CMOS 32-Bit Parallel CRC Engine,” IEEE Journal of Solid-State Circuits, Vol. 34, No. 2, pp. 233-235, February, 1999 discloses a mapping technology wherein a data width is expanded to 32 bits, a logic stage is minimized using a pre-decoding logic and a binary tree reduction scheme, and an XOR gate having a reduced fan-out is used in order to improve a speed.
A paper by M. D. Shieh et al., titled “A Systematic Approach for Parallel CRC Computations”, J. Information Science and Engineering, May, 2001 discloses a parallel CRC circuit based on Galois Field theory, and a paper by M. Spachmann, titled “Automatic Generation of Parallel CRC Circuits”, IEEE Design and Test of Computers, Vol. 18, pp. 108-114, May, 2001 discloses a VHDL code applicable to various generation polynomials and data widths.
The paper by G. Campobello, G. Patane and M. Russo, titled “Parallel CRC Realization,” IEEE Transactions on Computers, Vol. 52, pp. 63-71, October, 2003 discloses an optimized equation applicable to a case wherein the data width is equal to or lower than the order of the generation polynomial by improving the circuit disclosed in the paper by M. D. Shieh et al., which provides a high performance compared to the CRC circuit disclosed in the conventional papers.
However, the conventional parallel CRC circuit is difficult to be applied to a high speed data communication since a scheme for preventing a redundancy of the circuit or reducing a logic level for using a high clock frequency is not tried.
Therefore, a method for embodying an optimized CRC circuit that is applicable to every CRC circuit is needed.